In this notebook we compare the performance of:

  1. Image representation of kmer frequencies: 1.1. varKodes 1.2. Raw chaos game representation (CGR) (produced with code from idelucs) 1.3 CGR rescaled as in varKodes, using the new varKoder convert command

As an example, these are the 3 representations for the same sample:

representation example
varKode varKode example
raw CGR raw CGR example
rescaled CGR rescaled CGR example
  1. Neural network models: 2.1. ViT 2.2. ResneXT101_32x8d 2.3. Shallow 1D convolutional neural network from Fiannaca 2018 2.4. Multilayer perceptron (i. e. shallow fully connected network) from Arias 2022

In this test, we used the [development version of varKoder v1.0.0] (https://github.com/brunoasm/varKoder/commit/9b96d93815d18840c91d003d6b5226f6a93357af) for training and querying. We tested all combinations of these 2 aspects using leave-one-out cross-validation in the Malpighiales dataset and in this notebook we will compare their performances.

rm(list=ls())
library(tidyverse)
── Attaching core tidyverse packages ──────────────────────────────────────────────────────────────────────────────── tidyverse 2.0.0 ──
✔ dplyr     1.1.4     ✔ readr     2.1.5
✔ forcats   1.0.0     ✔ stringr   1.5.1
✔ ggplot2   3.4.4     ✔ tibble    3.2.1
✔ lubridate 1.9.3     ✔ tidyr     1.3.1
✔ purrr     1.0.2     ── Conflicts ────────────────────────────────────────────────────────────────────────────────────────────────── tidyverse_conflicts() ──
✖ dplyr::filter() masks stats::filter()
✖ dplyr::lag()    masks stats::lag()
ℹ Use the ]8;;http://conflicted.r-lib.org/conflicted package]8;; to force all conflicts to become errors
library(future)
library(ggthemes)
library(patchwork)
library(cowplot)

Attaching package: ‘cowplot’

The following object is masked from ‘package:patchwork’:

    align_plots

The following object is masked from ‘package:ggthemes’:

    theme_map

The following object is masked from ‘package:lubridate’:

    stamp
library(patchwork)
library(phytools)
Loading required package: ape

Attaching package: ‘ape’

The following object is masked from ‘package:dplyr’:

    where

Loading required package: maps

Attaching package: ‘maps’

The following object is masked from ‘package:purrr’:

    map
library(ape)
set.seed(14164)

Functions

read_and_process_xval = function(infolder,actual_labels=NULL){
  plan(multisession(workers = 4))
varkoder_results = list.files(infolder,
                                      'predictions.csv',
                                      recursive=T,
                                      full.names = T) %>%
  furrr::future_map_dfr(~read_csv(.x, show_col_types = FALSE) %>% mutate(sample_id = as.character(sample_id))) %>% 
  select(-1) %>%
  filter((query_basepairs %% 10^floor(log10(query_basepairs)) == 0) & 
           (query_basepairs / 10^floor(log10(query_basepairs)) %in% c(1, 2, 5))) %>% #we will ignore queries that are not standardized sizes
  rename(query_bp = query_basepairs) %>%
  mutate(quality_included = F)
plan(sequential)

if (!is.null(actual_labels)){
  varkoder_results = varkoder_results %>%
    select(-actual_labels) %>%
    left_join(select(actual_labels,sample_id,actual_labels) %>% distinct)
}

all_taxlabels = str_remove(varkoder_results$actual_labels,";*low_quality:True;*") %>% str_split(';') %>% unlist %>% unique

varkoder_results = varkoder_results %>%
  mutate(query_labels = str_remove(actual_labels,";*low_quality:True;*") %>% str_split(';'),
         predicted_list = str_split(predicted_labels,';')
         ) %>%
  rowwise() %>%
  mutate(family_correct = query_labels[str_detect(query_labels,'family')] %in% predicted_list,
         genus_correct = query_labels[str_detect(query_labels,'genus')] %in% predicted_list,
         species_correct = ifelse(any(str_detect(query_labels,'species')),
                                  query_labels[str_detect(query_labels,'species')] %in% predicted_list,
                                  NA
                                  ),
         family_incorrect = any(!(predicted_list[str_detect(predicted_list,'family')] %in% query_labels[str_detect(query_labels,'family')])),
         genus_incorrect = any(!(predicted_list[str_detect(predicted_list,'genus')] %in% query_labels[str_detect(query_labels,'genus')])),
         species_incorrect = ifelse(any(str_detect(query_labels,'species')),
                                  any(!(predicted_list[str_detect(predicted_list,'species')] %in% query_labels[str_detect(query_labels,'species')])),
                                  NA
                                  )
         
         )

return(varkoder_results)
}
summarize_results = function(res,level){
  res = res %>%
    ungroup() %>%
    mutate(low_quality = str_detect(actual_labels,"low_quality:True"),
           result = as.character(ifelse(res[,str_c(level,'correct',sep='_')] & !res[,str_c(level,'incorrect',sep='_')], 'correct',
                           ifelse(res[,str_c(level,'correct',sep='_')] & res[,str_c(level,'incorrect',sep='_')], 'ambiguous',
                                  ifelse(!res[,str_c(level,'correct',sep='_')]  & res[,str_c(level,'incorrect',sep='_')], 'incorrect',
                                                 'inconclusive'
                                  ))))
           ) %>%
    filter(!is.na(result)) %>%
    group_by(query_bp,result) %>%
    summarise(N=n(), .groups = 'drop') %>%
    group_by(query_bp) %>%
    mutate(p= N/sum(N)) %>%
    mutate(query_bp = as.integer(query_bp)) %>%
    ungroup() %>%
    mutate(query_bp = as.factor(query_bp)) %>%
    complete(query_bp,result, fill = list(p = 0, N = 0)) %>%
    mutate(query_bp = as.numeric(as.character(query_bp))) %>%
    ungroup()
    
  return(res)
}

calculate_precision_recall = function(results, taxonomic_level=NULL) {
  # Function to filter labels by taxonomic level
  filter_labels <- function(labels_list, level) {
    if (is.null(level)) {
      return(labels_list)
    } else {
      return(grep(paste0("^", level, ":"), labels_list, value = TRUE))
    }
  }

  # Filter rows and labels for a given taxonomic level
  filter_rows_and_labels <- function(results, level) {
    if (is.null(level)) {
      return(results)
    } else {
      # Keep only rows where the level is found in query_labels
      filtered_results <- results[sapply(results$query_labels, function(x) {
        any(grepl(paste0("^", level, ":"), x))
      }), ]

      # Filter labels in both query_labels and predicted_list
      filtered_results$query_labels <- lapply(filtered_results$query_labels, filter_labels, level)
      filtered_results$predicted_list <- lapply(filtered_results$predicted_list, filter_labels, level)

      return(filtered_results)
    }
  }

  # Apply filtering
  filtered_results <- filter_rows_and_labels(results, taxonomic_level)

  # Initialize counters for true positives, false positives, and false negatives
  total_true_positives <- 0
  total_false_positives <- 0
  total_false_negatives <- 0

  # Process each row in the filtered results
  for (i in seq_len(nrow(filtered_results))) {
    query_labels <- filtered_results$query_labels[[i]]
    predicted_labels <- filtered_results$predicted_list[[i]]

    true_positives <- sum(predicted_labels %in% query_labels)
    false_positives <- sum(!predicted_labels %in% query_labels & !is.na(predicted_labels) & predicted_labels != "")
    false_negatives <- sum(!query_labels %in% predicted_labels & !is.na(query_labels) & query_labels != "")

    # Update aggregate counts
    total_true_positives <- total_true_positives + true_positives
    total_false_positives <- total_false_positives + false_positives
    total_false_negatives <- total_false_negatives + false_negatives
  }

  # Calculate micro-averaged precision and recall
  micro_precision <- ifelse((total_true_positives + total_false_positives) > 0, 
                            total_true_positives / (total_true_positives + total_false_positives), 
                            NA_real_)
  micro_recall <- ifelse((total_true_positives + total_false_negatives) > 0, 
                         total_true_positives / (total_true_positives + total_false_negatives), 
                         NA_real_)

  return(tibble(taxonomic_level = taxonomic_level, 
                micro_precision = micro_precision, 
                micro_recall = micro_recall) %>%
           mutate(F1_score = 2 * (micro_precision * micro_recall) / (micro_precision + micro_recall)))
}
plot_area = function(sum_df, title, relative = FALSE, grid = TRUE, xlim_all = TRUE, wrap){
  breaks = c(500000,
             1000000,
             2000000,
             5000000,
             10000000,
             20000000,
             50000000,
             100000000,
             200000000
             )
  if (xlim_all){
    xlimits = range(breaks)
  } else {
    xlimits = range(sum_df$query_bp)
  }
  
  
  sum_df = sum_df %>%
    mutate(result = factor(result,ordered = T, levels = c('correct','ambiguous','inconclusive','incorrect'))) 
  if (relative){
    ylimits = c(0,1)
  } else {
    ylimits = c(0,sum_df %>% group_by(query_bp) %>% summarize(N=sum(N)) %>% pull(N) %>% max)
  }
  
  
  # Get colors from a Color Brewer palette
  brewer_colors <- RColorBrewer::brewer.pal(4, "Accent")
  
  if (relative) {
    p1 = ggplot(sum_df, aes(x=query_bp,y=p,fill=result)) +
    geom_area(position='stack') +
    scale_fill_manual(values = setNames(brewer_colors, c("correct", "ambiguous", "inconclusive", "incorrect"))) +
    scale_alpha_manual(values=c(0.5,1)) +
    scale_x_log10(labels = scales::label_number(scale_cut = scales::cut_si('bp')),breaks = breaks)  +
    scale_y_continuous() +
    ggtitle(title) +
    ylab('Fraction of samples') +
    xlab('Base pairs in query images') +
    theme_few() +
    theme(axis.text.x = element_text(hjust=1,angle=45))
  } else {
      p1 = ggplot(sum_df, aes(x=query_bp,y=N,fill=result)) +
    geom_area(position='stack') +
    scale_fill_manual(values = setNames(brewer_colors, c("correct", "ambiguous", "inconclusive", "incorrect"))) +
    scale_alpha_manual(values=c(0.5,1)) +
    scale_x_log10(labels = scales::label_number(scale_cut = scales::cut_si('bp')),breaks = breaks)   +
    scale_y_continuous() +
    ggtitle(title) +
    ylab('Number of samples') +
    xlab('Base pairs in query images') +
    theme_few() +
    theme(axis.text.x = element_text(hjust=1,angle=45))
  }
  
  if (grid){
    p1 = p1 +
      scale_y_continuous(n.breaks = 10, minor_breaks = waiver()) +
      theme(panel.background = element_rect(fill = NA),
            panel.grid.major.y = element_line(colour = gray(0.5)),
            panel.grid.minor.y = element_line(colour = gray(0.6),linetype = 2),
            panel.ontop = TRUE)
  }
  
  p1 = p1 + coord_cartesian(xlim=xlimits, ylim=ylimits,expand = FALSE)
  
  if (!missing(wrap)) {
    p1 = p1 + facet_wrap(as.formula(wrap))
  }
  
  return(p1)
}
  
representations = c('cgr_varKoder','varKodes','cgr_idelucs')
models = c('vit_large_patch32_224','ig_resnext101_32x8d','fiannaca2018','arias2022')
ranks = c('species','genus','family')

Now let’s plot genus-level accuracy for all models:

results = list()
summaries = list()
precision_recall = list()
plots = list()

for (rep in representations){
  for (mod in models){
    if (rep != 'cgr_idelucs' ){
      results[[paste(rep,mod,sep='+')]] = read_and_process_xval(paste('results',rep,mod,sep='_'))
    } else {
      results[[paste(rep,mod,sep='+')]] = read_and_process_xval(paste('results',rep,mod,sep='_'),
                                                                results[[paste('cgr_varKoder',mod,sep='+')]])
    }
    
    for (rk in ranks){
      summaries[[paste(rk,rep,mod,sep='+')]] = summarize_results(results[[paste(rep,mod,sep='+')]],rk)
      precision_recall[[paste(rk,rep,mod,sep='+')]] = calculate_precision_recall(results[[paste(rep,mod,sep='+')]],rk)
      plots[[paste(rk,rep,mod,sep='+')]]  = suppressMessages({plot_area(summaries[[paste(rk,rep,mod,sep='+')]], paste(rk,rep,mod), relative = TRUE)})
    }
  }
}

Let’s now look at all plots.

plots
$`species+cgr_varKoder+vit_large_patch32_224`

$`genus+cgr_varKoder+vit_large_patch32_224`

$`family+cgr_varKoder+vit_large_patch32_224`

$`species+cgr_varKoder+ig_resnext101_32x8d`

$`genus+cgr_varKoder+ig_resnext101_32x8d`

$`family+cgr_varKoder+ig_resnext101_32x8d`

$`species+cgr_varKoder+fiannaca2018`

$`genus+cgr_varKoder+fiannaca2018`

$`family+cgr_varKoder+fiannaca2018`

$`species+cgr_varKoder+arias2022`

$`genus+cgr_varKoder+arias2022`

$`family+cgr_varKoder+arias2022`

$`species+varKodes+vit_large_patch32_224`

$`genus+varKodes+vit_large_patch32_224`

$`family+varKodes+vit_large_patch32_224`

$`species+varKodes+ig_resnext101_32x8d`

$`genus+varKodes+ig_resnext101_32x8d`

$`family+varKodes+ig_resnext101_32x8d`

$`species+varKodes+fiannaca2018`

$`genus+varKodes+fiannaca2018`

$`family+varKodes+fiannaca2018`

$`species+varKodes+arias2022`

$`genus+varKodes+arias2022`

$`family+varKodes+arias2022`

$`species+cgr_idelucs+vit_large_patch32_224`

$`genus+cgr_idelucs+vit_large_patch32_224`

$`family+cgr_idelucs+vit_large_patch32_224`

$`species+cgr_idelucs+ig_resnext101_32x8d`

$`genus+cgr_idelucs+ig_resnext101_32x8d`

$`family+cgr_idelucs+ig_resnext101_32x8d`

$`species+cgr_idelucs+fiannaca2018`

$`genus+cgr_idelucs+fiannaca2018`

$`family+cgr_idelucs+fiannaca2018`

$`species+cgr_idelucs+arias2022`

$`genus+cgr_idelucs+arias2022`

$`family+cgr_idelucs+arias2022`

Function to arrange plots nicely:

library(ggplot2)
library(patchwork)

arrange_tax_plots <- function(plot_list, tax_level = "species") {
  # Validate tax_level
  valid_levels <- c("species", "genus", "family")
  if (!tax_level %in% valid_levels) {
    stop("tax_level must be one of: ", paste(valid_levels, collapse = ", "))
  }
  
  # Get names of plots for specified taxonomic level
  tax_names <- names(plot_list)[grep(paste0("^", tax_level, "\\+"), names(plot_list))]
  
  # Create mapping for ordering
  models <- c("vit_large_patch32_224", "ig_resnext101_32x8d", "fiannaca2018", "arias2022")
  representations <- c("cgr_idelucs", "cgr_varKoder", "varKodes")
  
  # Create empty matrix to store plot indices
  plot_matrix <- matrix(NA, nrow = length(representations), ncol = length(models))
  rownames(plot_matrix) <- representations
  colnames(plot_matrix) <- models
  
  # Fill matrix with plot indices
  for (rep in representations) {
    for (mod in models) {
      plot_name <- tax_names[grep(paste0(rep, ".*", mod, "$"), tax_names)]
      if (length(plot_name) > 0) {
        plot_matrix[rep, mod] <- which(names(plot_list) == plot_name)
      }
    }
  }
  
  # Extract plots in correct order
  plot_indices <- as.vector(t(plot_matrix))
  selected_plots <- plot_list[plot_indices]
  
  # Create the layout manually
  combined_plot <- selected_plots[[1]]
  for(i in 2:length(selected_plots)) {
    combined_plot <- combined_plot + selected_plots[[i]]
  }
  
  # Apply layout and theme
  combined_plot <- combined_plot + 
    plot_layout(ncol = 4, guides = "collect") &
    theme(
      axis.text.x = element_blank(),
      axis.ticks.x = element_blank(),
      axis.title = element_blank(),
      plot.title = element_blank(),
      text = element_text(size=8),
      legend.position = 'bottom'
    )
  
  # Add back necessary axis elements
  for(i in seq_along(selected_plots)) {
    # Left column: add y-axis text
    if(i %in% seq(1, 9, by = 4)) {
      combined_plot[[i]] <- combined_plot[[i]] + 
        theme(axis.text.y = element_text())
    } else {
      combined_plot[[i]] <- combined_plot[[i]] + 
        theme(axis.text.y = element_blank())
    }
    
    # Bottom row: add x-axis text at 45 degrees
    if(i %in% 9:12) {
      combined_plot[[i]] <- combined_plot[[i]] + 
        theme(
          axis.text.x = element_text(angle = 45, hjust = 1,vjust=1),
          axis.ticks.x = element_line()
        )
    }
  }
  
  return(combined_plot)
}

# Example usage:
# species_plot <- arrange_tax_plots(plot_list, "species")
# ggsave("species_plots.pdf", species_plot, width = 16, height = 12)

Species:

arrange_tax_plots(plots, "species")
ggsave(device = 'pdf',filename = 'species_comparison.pdf',width = 183,height = 160,units = 'mm')

Now let’s compare precision and recall for each taxonomic level. First, species:


options(tibble.print_max = Inf) 

df = imap_dfr(precision_recall, ~ mutate(.x, list_element = .y)) %>%
  separate(list_element, into = c("taxonomy", "representation", "model"), sep = "\\+", extra = "merge", fill = "right") %>%
  select(-taxonomy) %>%
   arrange(taxonomic_level,desc(F1_score))

split_dfs <- split(df, df$taxonomic_level)

split_dfs

It seems the multi-layer perceptron (arias2022) had very low accuracy. Let’s have a look at the details to understand:

results$`varKodes+arias2022`

It seems the correct taxa may have higher probability, but not high enough to pass our 0.7 threshold. On the other hand, incorrect taxa have generally lower probability, but pretty high still (0.3-0.5). So the model has some trouble discriminating classes in a multilabel model.

Let’s now save the comparison table as a csv to add as a supplement to the paper.

write_csv(df, 'arch_rep_results.csv')
LS0tCnRpdGxlOiAiQ3Jvc3MtdmFsaWRhdGlvbiB0byB0ZXN0IHZhcktvZGVyIGFnYWluc3QgTk4gYWx0ZXJuYXRpdmVzIgpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sKLS0tCgpJbiB0aGlzIG5vdGVib29rIHdlIGNvbXBhcmUgdGhlIHBlcmZvcm1hbmNlIG9mOgoKIDEuIEltYWdlIHJlcHJlc2VudGF0aW9uIG9mIGttZXIgZnJlcXVlbmNpZXM6CiAgIDEuMS4gdmFyS29kZXMKICAgMS4yLiBSYXcgY2hhb3MgZ2FtZSByZXByZXNlbnRhdGlvbiAoQ0dSKSAocHJvZHVjZWQgd2l0aCBjb2RlIGZyb20gW2lkZWx1Y3NdKGh0dHBzOi8vZ2l0aHViLmNvbS9LYXJpLUdlbm9taWNzLUxhYi9pRGVMVUNTKSkKICAgMS4zIENHUiByZXNjYWxlZCBhcyBpbiB2YXJLb2RlcywgdXNpbmcgdGhlIG5ldyBgdmFyS29kZXIgY29udmVydGAgY29tbWFuZAogICAKICAgQXMgYW4gZXhhbXBsZSwgdGhlc2UgYXJlIHRoZSAzIHJlcHJlc2VudGF0aW9ucyBmb3IgdGhlIHNhbWUgc2FtcGxlOgogICAKICAgCnwgcmVwcmVzZW50YXRpb24gfCBleGFtcGxlIHwKfCAtLS0tLS0tLS0tLS0tLSB8IC0tLS0tLS0gfAp8IHZhcktvZGUgICAgICAgIHwgIVt2YXJLb2RlIGV4YW1wbGVdKC4vZGF0YXNldHMvdmFyS29kZXMvMTA4OUAwMDAzNDMyMksrazcucG5nKSB8CnwgcmF3IENHUiAgICAgICAgfCAhW3JhdyBDR1IgZXhhbXBsZV0oLi9kYXRhc2V0cy9jZ3JfaWRlbHVjcy8xMDg5QDAwMDM0MzIySytrNy5wbmcpIHwKfCByZXNjYWxlZCBDR1IgICB8ICFbcmVzY2FsZWQgQ0dSIGV4YW1wbGVdKC4vZGF0YXNldHMvY2dyX3ZhcktvZGVyLzEwODlAMDAwMzQzMjJLK2NncitrNy5wbmcpIHwKCgoyLiBOZXVyYWwgbmV0d29yayBtb2RlbHM6CiAgMi4xLiBWaVQKICAyLjIuIFJlc25lWFQxMDFfMzJ4OGQKICAyLjMuIFNoYWxsb3cgMUQgY29udm9sdXRpb25hbCBuZXVyYWwgbmV0d29yayBmcm9tIFtGaWFubmFjYSAyMDE4XShodHRwczovL3B1Ym1lZC5uY2JpLm5sbS5uaWguZ292LzMwMDY2NjI5LykKICAyLjQuIE11bHRpbGF5ZXIgcGVyY2VwdHJvbiAoaS4gZS4gc2hhbGxvdyBmdWxseSBjb25uZWN0ZWQgbmV0d29yaykgZnJvbSBbQXJpYXMgMjAyMl0oaHR0cHM6Ly93d3cubmNiaS5ubG0ubmloLmdvdi9wbWMvYXJ0aWNsZXMvUE1DODc4MjMwNy8pCiAgCkluIHRoaXMgdGVzdCwgd2UgdXNlZCB0aGUgW2RldmVsb3BtZW50IHZlcnNpb24gb2YgdmFyS29kZXIgdjEuMC4wXSAoaHR0cHM6Ly9naXRodWIuY29tL2JydW5vYXNtL3ZhcktvZGVyL2NvbW1pdC85Yjk2ZDkzODE1ZDE4ODQwYzkxZDAwM2Q2YjUyMjZmNmE5MzM1N2FmKSBmb3IgdHJhaW5pbmcgYW5kIHF1ZXJ5aW5nLiBXZSB0ZXN0ZWQgYWxsIGNvbWJpbmF0aW9ucyBvZiB0aGVzZSAyIGFzcGVjdHMgdXNpbmcgbGVhdmUtb25lLW91dCBjcm9zcy12YWxpZGF0aW9uIGluIHRoZSBNYWxwaWdoaWFsZXMgZGF0YXNldCBhbmQgaW4gdGhpcyBub3RlYm9vayB3ZSB3aWxsIGNvbXBhcmUgdGhlaXIgcGVyZm9ybWFuY2VzLgoKYGBge3J9CnJtKGxpc3Q9bHMoKSkKbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkoZnV0dXJlKQpsaWJyYXJ5KGdndGhlbWVzKQpsaWJyYXJ5KHBhdGNod29yaykKbGlicmFyeShjb3dwbG90KQpsaWJyYXJ5KHBhdGNod29yaykKbGlicmFyeShwaHl0b29scykKbGlicmFyeShhcGUpCnNldC5zZWVkKDE0MTY0KQpgYGAKIyBGdW5jdGlvbnMKCgpgYGB7cn0KcmVhZF9hbmRfcHJvY2Vzc194dmFsID0gZnVuY3Rpb24oaW5mb2xkZXIsYWN0dWFsX2xhYmVscz1OVUxMKXsKICBwbGFuKG11bHRpc2Vzc2lvbih3b3JrZXJzID0gNCkpCnZhcmtvZGVyX3Jlc3VsdHMgPSBsaXN0LmZpbGVzKGluZm9sZGVyLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICdwcmVkaWN0aW9ucy5jc3YnLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlY3Vyc2l2ZT1ULAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGZ1bGwubmFtZXMgPSBUKSAlPiUKICBmdXJycjo6ZnV0dXJlX21hcF9kZnIofnJlYWRfY3N2KC54LCBzaG93X2NvbF90eXBlcyA9IEZBTFNFKSAlPiUgbXV0YXRlKHNhbXBsZV9pZCA9IGFzLmNoYXJhY3RlcihzYW1wbGVfaWQpKSkgJT4lIAogIHNlbGVjdCgtMSkgJT4lCiAgZmlsdGVyKChxdWVyeV9iYXNlcGFpcnMgJSUgMTBeZmxvb3IobG9nMTAocXVlcnlfYmFzZXBhaXJzKSkgPT0gMCkgJiAKICAgICAgICAgICAocXVlcnlfYmFzZXBhaXJzIC8gMTBeZmxvb3IobG9nMTAocXVlcnlfYmFzZXBhaXJzKSkgJWluJSBjKDEsIDIsIDUpKSkgJT4lICN3ZSB3aWxsIGlnbm9yZSBxdWVyaWVzIHRoYXQgYXJlIG5vdCBzdGFuZGFyZGl6ZWQgc2l6ZXMKICByZW5hbWUocXVlcnlfYnAgPSBxdWVyeV9iYXNlcGFpcnMpICU+JQogIG11dGF0ZShxdWFsaXR5X2luY2x1ZGVkID0gRikKcGxhbihzZXF1ZW50aWFsKQoKaWYgKCFpcy5udWxsKGFjdHVhbF9sYWJlbHMpKXsKICB2YXJrb2Rlcl9yZXN1bHRzID0gdmFya29kZXJfcmVzdWx0cyAlPiUKICAgIHNlbGVjdCgtYWN0dWFsX2xhYmVscykgJT4lCiAgICBsZWZ0X2pvaW4oc2VsZWN0KGFjdHVhbF9sYWJlbHMsc2FtcGxlX2lkLGFjdHVhbF9sYWJlbHMpICU+JSBkaXN0aW5jdCkKfQoKYWxsX3RheGxhYmVscyA9IHN0cl9yZW1vdmUodmFya29kZXJfcmVzdWx0cyRhY3R1YWxfbGFiZWxzLCI7Kmxvd19xdWFsaXR5OlRydWU7KiIpICU+JSBzdHJfc3BsaXQoJzsnKSAlPiUgdW5saXN0ICU+JSB1bmlxdWUKCnZhcmtvZGVyX3Jlc3VsdHMgPSB2YXJrb2Rlcl9yZXN1bHRzICU+JQogIG11dGF0ZShxdWVyeV9sYWJlbHMgPSBzdHJfcmVtb3ZlKGFjdHVhbF9sYWJlbHMsIjsqbG93X3F1YWxpdHk6VHJ1ZTsqIikgJT4lIHN0cl9zcGxpdCgnOycpLAogICAgICAgICBwcmVkaWN0ZWRfbGlzdCA9IHN0cl9zcGxpdChwcmVkaWN0ZWRfbGFiZWxzLCc7JykKICAgICAgICAgKSAlPiUKICByb3d3aXNlKCkgJT4lCiAgbXV0YXRlKGZhbWlseV9jb3JyZWN0ID0gcXVlcnlfbGFiZWxzW3N0cl9kZXRlY3QocXVlcnlfbGFiZWxzLCdmYW1pbHknKV0gJWluJSBwcmVkaWN0ZWRfbGlzdCwKICAgICAgICAgZ2VudXNfY29ycmVjdCA9IHF1ZXJ5X2xhYmVsc1tzdHJfZGV0ZWN0KHF1ZXJ5X2xhYmVscywnZ2VudXMnKV0gJWluJSBwcmVkaWN0ZWRfbGlzdCwKICAgICAgICAgc3BlY2llc19jb3JyZWN0ID0gaWZlbHNlKGFueShzdHJfZGV0ZWN0KHF1ZXJ5X2xhYmVscywnc3BlY2llcycpKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHF1ZXJ5X2xhYmVsc1tzdHJfZGV0ZWN0KHF1ZXJ5X2xhYmVscywnc3BlY2llcycpXSAlaW4lIHByZWRpY3RlZF9saXN0LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgTkEKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICksCiAgICAgICAgIGZhbWlseV9pbmNvcnJlY3QgPSBhbnkoIShwcmVkaWN0ZWRfbGlzdFtzdHJfZGV0ZWN0KHByZWRpY3RlZF9saXN0LCdmYW1pbHknKV0gJWluJSBxdWVyeV9sYWJlbHNbc3RyX2RldGVjdChxdWVyeV9sYWJlbHMsJ2ZhbWlseScpXSkpLAogICAgICAgICBnZW51c19pbmNvcnJlY3QgPSBhbnkoIShwcmVkaWN0ZWRfbGlzdFtzdHJfZGV0ZWN0KHByZWRpY3RlZF9saXN0LCdnZW51cycpXSAlaW4lIHF1ZXJ5X2xhYmVsc1tzdHJfZGV0ZWN0KHF1ZXJ5X2xhYmVscywnZ2VudXMnKV0pKSwKICAgICAgICAgc3BlY2llc19pbmNvcnJlY3QgPSBpZmVsc2UoYW55KHN0cl9kZXRlY3QocXVlcnlfbGFiZWxzLCdzcGVjaWVzJykpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYW55KCEocHJlZGljdGVkX2xpc3Rbc3RyX2RldGVjdChwcmVkaWN0ZWRfbGlzdCwnc3BlY2llcycpXSAlaW4lIHF1ZXJ5X2xhYmVsc1tzdHJfZGV0ZWN0KHF1ZXJ5X2xhYmVscywnc3BlY2llcycpXSkpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgTkEKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICkKICAgICAgICAgCiAgICAgICAgICkKCnJldHVybih2YXJrb2Rlcl9yZXN1bHRzKQp9CmBgYAoKCmBgYHtyfQpzdW1tYXJpemVfcmVzdWx0cyA9IGZ1bmN0aW9uKHJlcyxsZXZlbCl7CiAgcmVzID0gcmVzICU+JQogICAgdW5ncm91cCgpICU+JQogICAgbXV0YXRlKGxvd19xdWFsaXR5ID0gc3RyX2RldGVjdChhY3R1YWxfbGFiZWxzLCJsb3dfcXVhbGl0eTpUcnVlIiksCiAgICAgICAgICAgcmVzdWx0ID0gYXMuY2hhcmFjdGVyKGlmZWxzZShyZXNbLHN0cl9jKGxldmVsLCdjb3JyZWN0JyxzZXA9J18nKV0gJiAhcmVzWyxzdHJfYyhsZXZlbCwnaW5jb3JyZWN0JyxzZXA9J18nKV0sICdjb3JyZWN0JywKICAgICAgICAgICAgICAgICAgICAgICAgICAgaWZlbHNlKHJlc1ssc3RyX2MobGV2ZWwsJ2NvcnJlY3QnLHNlcD0nXycpXSAmIHJlc1ssc3RyX2MobGV2ZWwsJ2luY29ycmVjdCcsc2VwPSdfJyldLCAnYW1iaWd1b3VzJywKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmZWxzZSghcmVzWyxzdHJfYyhsZXZlbCwnY29ycmVjdCcsc2VwPSdfJyldICAmIHJlc1ssc3RyX2MobGV2ZWwsJ2luY29ycmVjdCcsc2VwPSdfJyldLCAnaW5jb3JyZWN0JywKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICdpbmNvbmNsdXNpdmUnCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICApKSkpCiAgICAgICAgICAgKSAlPiUKICAgIGZpbHRlcighaXMubmEocmVzdWx0KSkgJT4lCiAgICBncm91cF9ieShxdWVyeV9icCxyZXN1bHQpICU+JQogICAgc3VtbWFyaXNlKE49bigpLCAuZ3JvdXBzID0gJ2Ryb3AnKSAlPiUKICAgIGdyb3VwX2J5KHF1ZXJ5X2JwKSAlPiUKICAgIG11dGF0ZShwPSBOL3N1bShOKSkgJT4lCiAgICBtdXRhdGUocXVlcnlfYnAgPSBhcy5pbnRlZ2VyKHF1ZXJ5X2JwKSkgJT4lCiAgICB1bmdyb3VwKCkgJT4lCiAgICBtdXRhdGUocXVlcnlfYnAgPSBhcy5mYWN0b3IocXVlcnlfYnApKSAlPiUKICAgIGNvbXBsZXRlKHF1ZXJ5X2JwLHJlc3VsdCwgZmlsbCA9IGxpc3QocCA9IDAsIE4gPSAwKSkgJT4lCiAgICBtdXRhdGUocXVlcnlfYnAgPSBhcy5udW1lcmljKGFzLmNoYXJhY3RlcihxdWVyeV9icCkpKSAlPiUKICAgIHVuZ3JvdXAoKQogICAgCiAgcmV0dXJuKHJlcykKfQpgYGAKCmBgYHtyfQoKY2FsY3VsYXRlX3ByZWNpc2lvbl9yZWNhbGwgPSBmdW5jdGlvbihyZXN1bHRzLCB0YXhvbm9taWNfbGV2ZWw9TlVMTCkgewogICMgRnVuY3Rpb24gdG8gZmlsdGVyIGxhYmVscyBieSB0YXhvbm9taWMgbGV2ZWwKICBmaWx0ZXJfbGFiZWxzIDwtIGZ1bmN0aW9uKGxhYmVsc19saXN0LCBsZXZlbCkgewogICAgaWYgKGlzLm51bGwobGV2ZWwpKSB7CiAgICAgIHJldHVybihsYWJlbHNfbGlzdCkKICAgIH0gZWxzZSB7CiAgICAgIHJldHVybihncmVwKHBhc3RlMCgiXiIsIGxldmVsLCAiOiIpLCBsYWJlbHNfbGlzdCwgdmFsdWUgPSBUUlVFKSkKICAgIH0KICB9CgogICMgRmlsdGVyIHJvd3MgYW5kIGxhYmVscyBmb3IgYSBnaXZlbiB0YXhvbm9taWMgbGV2ZWwKICBmaWx0ZXJfcm93c19hbmRfbGFiZWxzIDwtIGZ1bmN0aW9uKHJlc3VsdHMsIGxldmVsKSB7CiAgICBpZiAoaXMubnVsbChsZXZlbCkpIHsKICAgICAgcmV0dXJuKHJlc3VsdHMpCiAgICB9IGVsc2UgewogICAgICAjIEtlZXAgb25seSByb3dzIHdoZXJlIHRoZSBsZXZlbCBpcyBmb3VuZCBpbiBxdWVyeV9sYWJlbHMKICAgICAgZmlsdGVyZWRfcmVzdWx0cyA8LSByZXN1bHRzW3NhcHBseShyZXN1bHRzJHF1ZXJ5X2xhYmVscywgZnVuY3Rpb24oeCkgewogICAgICAgIGFueShncmVwbChwYXN0ZTAoIl4iLCBsZXZlbCwgIjoiKSwgeCkpCiAgICAgIH0pLCBdCgogICAgICAjIEZpbHRlciBsYWJlbHMgaW4gYm90aCBxdWVyeV9sYWJlbHMgYW5kIHByZWRpY3RlZF9saXN0CiAgICAgIGZpbHRlcmVkX3Jlc3VsdHMkcXVlcnlfbGFiZWxzIDwtIGxhcHBseShmaWx0ZXJlZF9yZXN1bHRzJHF1ZXJ5X2xhYmVscywgZmlsdGVyX2xhYmVscywgbGV2ZWwpCiAgICAgIGZpbHRlcmVkX3Jlc3VsdHMkcHJlZGljdGVkX2xpc3QgPC0gbGFwcGx5KGZpbHRlcmVkX3Jlc3VsdHMkcHJlZGljdGVkX2xpc3QsIGZpbHRlcl9sYWJlbHMsIGxldmVsKQoKICAgICAgcmV0dXJuKGZpbHRlcmVkX3Jlc3VsdHMpCiAgICB9CiAgfQoKICAjIEFwcGx5IGZpbHRlcmluZwogIGZpbHRlcmVkX3Jlc3VsdHMgPC0gZmlsdGVyX3Jvd3NfYW5kX2xhYmVscyhyZXN1bHRzLCB0YXhvbm9taWNfbGV2ZWwpCgogICMgSW5pdGlhbGl6ZSBjb3VudGVycyBmb3IgdHJ1ZSBwb3NpdGl2ZXMsIGZhbHNlIHBvc2l0aXZlcywgYW5kIGZhbHNlIG5lZ2F0aXZlcwogIHRvdGFsX3RydWVfcG9zaXRpdmVzIDwtIDAKICB0b3RhbF9mYWxzZV9wb3NpdGl2ZXMgPC0gMAogIHRvdGFsX2ZhbHNlX25lZ2F0aXZlcyA8LSAwCgogICMgUHJvY2VzcyBlYWNoIHJvdyBpbiB0aGUgZmlsdGVyZWQgcmVzdWx0cwogIGZvciAoaSBpbiBzZXFfbGVuKG5yb3coZmlsdGVyZWRfcmVzdWx0cykpKSB7CiAgICBxdWVyeV9sYWJlbHMgPC0gZmlsdGVyZWRfcmVzdWx0cyRxdWVyeV9sYWJlbHNbW2ldXQogICAgcHJlZGljdGVkX2xhYmVscyA8LSBmaWx0ZXJlZF9yZXN1bHRzJHByZWRpY3RlZF9saXN0W1tpXV0KCiAgICB0cnVlX3Bvc2l0aXZlcyA8LSBzdW0ocHJlZGljdGVkX2xhYmVscyAlaW4lIHF1ZXJ5X2xhYmVscykKICAgIGZhbHNlX3Bvc2l0aXZlcyA8LSBzdW0oIXByZWRpY3RlZF9sYWJlbHMgJWluJSBxdWVyeV9sYWJlbHMgJiAhaXMubmEocHJlZGljdGVkX2xhYmVscykgJiBwcmVkaWN0ZWRfbGFiZWxzICE9ICIiKQogICAgZmFsc2VfbmVnYXRpdmVzIDwtIHN1bSghcXVlcnlfbGFiZWxzICVpbiUgcHJlZGljdGVkX2xhYmVscyAmICFpcy5uYShxdWVyeV9sYWJlbHMpICYgcXVlcnlfbGFiZWxzICE9ICIiKQoKICAgICMgVXBkYXRlIGFnZ3JlZ2F0ZSBjb3VudHMKICAgIHRvdGFsX3RydWVfcG9zaXRpdmVzIDwtIHRvdGFsX3RydWVfcG9zaXRpdmVzICsgdHJ1ZV9wb3NpdGl2ZXMKICAgIHRvdGFsX2ZhbHNlX3Bvc2l0aXZlcyA8LSB0b3RhbF9mYWxzZV9wb3NpdGl2ZXMgKyBmYWxzZV9wb3NpdGl2ZXMKICAgIHRvdGFsX2ZhbHNlX25lZ2F0aXZlcyA8LSB0b3RhbF9mYWxzZV9uZWdhdGl2ZXMgKyBmYWxzZV9uZWdhdGl2ZXMKICB9CgogICMgQ2FsY3VsYXRlIG1pY3JvLWF2ZXJhZ2VkIHByZWNpc2lvbiBhbmQgcmVjYWxsCiAgbWljcm9fcHJlY2lzaW9uIDwtIGlmZWxzZSgodG90YWxfdHJ1ZV9wb3NpdGl2ZXMgKyB0b3RhbF9mYWxzZV9wb3NpdGl2ZXMpID4gMCwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB0b3RhbF90cnVlX3Bvc2l0aXZlcyAvICh0b3RhbF90cnVlX3Bvc2l0aXZlcyArIHRvdGFsX2ZhbHNlX3Bvc2l0aXZlcyksIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgTkFfcmVhbF8pCiAgbWljcm9fcmVjYWxsIDwtIGlmZWxzZSgodG90YWxfdHJ1ZV9wb3NpdGl2ZXMgKyB0b3RhbF9mYWxzZV9uZWdhdGl2ZXMpID4gMCwgCiAgICAgICAgICAgICAgICAgICAgICAgICB0b3RhbF90cnVlX3Bvc2l0aXZlcyAvICh0b3RhbF90cnVlX3Bvc2l0aXZlcyArIHRvdGFsX2ZhbHNlX25lZ2F0aXZlcyksIAogICAgICAgICAgICAgICAgICAgICAgICAgTkFfcmVhbF8pCgogIHJldHVybih0aWJibGUodGF4b25vbWljX2xldmVsID0gdGF4b25vbWljX2xldmVsLCAKICAgICAgICAgICAgICAgIG1pY3JvX3ByZWNpc2lvbiA9IG1pY3JvX3ByZWNpc2lvbiwgCiAgICAgICAgICAgICAgICBtaWNyb19yZWNhbGwgPSBtaWNyb19yZWNhbGwpICU+JQogICAgICAgICAgIG11dGF0ZShGMV9zY29yZSA9IDIgKiAobWljcm9fcHJlY2lzaW9uICogbWljcm9fcmVjYWxsKSAvIChtaWNyb19wcmVjaXNpb24gKyBtaWNyb19yZWNhbGwpKSkKfQpgYGAKCgoKYGBge3J9CnBsb3RfYXJlYSA9IGZ1bmN0aW9uKHN1bV9kZiwgdGl0bGUsIHJlbGF0aXZlID0gRkFMU0UsIGdyaWQgPSBUUlVFLCB4bGltX2FsbCA9IFRSVUUsIHdyYXApewogIGJyZWFrcyA9IGMoNTAwMDAwLAogICAgICAgICAgICAgMTAwMDAwMCwKICAgICAgICAgICAgIDIwMDAwMDAsCiAgICAgICAgICAgICA1MDAwMDAwLAogICAgICAgICAgICAgMTAwMDAwMDAsCiAgICAgICAgICAgICAyMDAwMDAwMCwKICAgICAgICAgICAgIDUwMDAwMDAwLAogICAgICAgICAgICAgMTAwMDAwMDAwLAogICAgICAgICAgICAgMjAwMDAwMDAwCiAgICAgICAgICAgICApCiAgaWYgKHhsaW1fYWxsKXsKICAgIHhsaW1pdHMgPSByYW5nZShicmVha3MpCiAgfSBlbHNlIHsKICAgIHhsaW1pdHMgPSByYW5nZShzdW1fZGYkcXVlcnlfYnApCiAgfQogIAogIAogIHN1bV9kZiA9IHN1bV9kZiAlPiUKICAgIG11dGF0ZShyZXN1bHQgPSBmYWN0b3IocmVzdWx0LG9yZGVyZWQgPSBULCBsZXZlbHMgPSBjKCdjb3JyZWN0JywnYW1iaWd1b3VzJywnaW5jb25jbHVzaXZlJywnaW5jb3JyZWN0JykpKSAKICBpZiAocmVsYXRpdmUpewogICAgeWxpbWl0cyA9IGMoMCwxKQogIH0gZWxzZSB7CiAgICB5bGltaXRzID0gYygwLHN1bV9kZiAlPiUgZ3JvdXBfYnkocXVlcnlfYnApICU+JSBzdW1tYXJpemUoTj1zdW0oTikpICU+JSBwdWxsKE4pICU+JSBtYXgpCiAgfQogIAogIAogICMgR2V0IGNvbG9ycyBmcm9tIGEgQ29sb3IgQnJld2VyIHBhbGV0dGUKICBicmV3ZXJfY29sb3JzIDwtIFJDb2xvckJyZXdlcjo6YnJld2VyLnBhbCg0LCAiQWNjZW50IikKICAKICBpZiAocmVsYXRpdmUpIHsKICAgIHAxID0gZ2dwbG90KHN1bV9kZiwgYWVzKHg9cXVlcnlfYnAseT1wLGZpbGw9cmVzdWx0KSkgKwogICAgZ2VvbV9hcmVhKHBvc2l0aW9uPSdzdGFjaycpICsKICAgIHNjYWxlX2ZpbGxfbWFudWFsKHZhbHVlcyA9IHNldE5hbWVzKGJyZXdlcl9jb2xvcnMsIGMoImNvcnJlY3QiLCAiYW1iaWd1b3VzIiwgImluY29uY2x1c2l2ZSIsICJpbmNvcnJlY3QiKSkpICsKICAgIHNjYWxlX2FscGhhX21hbnVhbCh2YWx1ZXM9YygwLjUsMSkpICsKICAgIHNjYWxlX3hfbG9nMTAobGFiZWxzID0gc2NhbGVzOjpsYWJlbF9udW1iZXIoc2NhbGVfY3V0ID0gc2NhbGVzOjpjdXRfc2koJ2JwJykpLGJyZWFrcyA9IGJyZWFrcykgICsKICAgIHNjYWxlX3lfY29udGludW91cygpICsKICAgIGdndGl0bGUodGl0bGUpICsKICAgIHlsYWIoJ0ZyYWN0aW9uIG9mIHNhbXBsZXMnKSArCiAgICB4bGFiKCdCYXNlIHBhaXJzIGluIHF1ZXJ5IGltYWdlcycpICsKICAgIHRoZW1lX2ZldygpICsKICAgIHRoZW1lKGF4aXMudGV4dC54ID0gZWxlbWVudF90ZXh0KGhqdXN0PTEsYW5nbGU9NDUpKQogIH0gZWxzZSB7CiAgICAgIHAxID0gZ2dwbG90KHN1bV9kZiwgYWVzKHg9cXVlcnlfYnAseT1OLGZpbGw9cmVzdWx0KSkgKwogICAgZ2VvbV9hcmVhKHBvc2l0aW9uPSdzdGFjaycpICsKICAgIHNjYWxlX2ZpbGxfbWFudWFsKHZhbHVlcyA9IHNldE5hbWVzKGJyZXdlcl9jb2xvcnMsIGMoImNvcnJlY3QiLCAiYW1iaWd1b3VzIiwgImluY29uY2x1c2l2ZSIsICJpbmNvcnJlY3QiKSkpICsKICAgIHNjYWxlX2FscGhhX21hbnVhbCh2YWx1ZXM9YygwLjUsMSkpICsKICAgIHNjYWxlX3hfbG9nMTAobGFiZWxzID0gc2NhbGVzOjpsYWJlbF9udW1iZXIoc2NhbGVfY3V0ID0gc2NhbGVzOjpjdXRfc2koJ2JwJykpLGJyZWFrcyA9IGJyZWFrcykgICArCiAgICBzY2FsZV95X2NvbnRpbnVvdXMoKSArCiAgICBnZ3RpdGxlKHRpdGxlKSArCiAgICB5bGFiKCdOdW1iZXIgb2Ygc2FtcGxlcycpICsKICAgIHhsYWIoJ0Jhc2UgcGFpcnMgaW4gcXVlcnkgaW1hZ2VzJykgKwogICAgdGhlbWVfZmV3KCkgKwogICAgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoaGp1c3Q9MSxhbmdsZT00NSkpCiAgfQogIAogIGlmIChncmlkKXsKICAgIHAxID0gcDEgKwogICAgICBzY2FsZV95X2NvbnRpbnVvdXMobi5icmVha3MgPSAxMCwgbWlub3JfYnJlYWtzID0gd2FpdmVyKCkpICsKICAgICAgdGhlbWUocGFuZWwuYmFja2dyb3VuZCA9IGVsZW1lbnRfcmVjdChmaWxsID0gTkEpLAogICAgICAgICAgICBwYW5lbC5ncmlkLm1ham9yLnkgPSBlbGVtZW50X2xpbmUoY29sb3VyID0gZ3JheSgwLjUpKSwKICAgICAgICAgICAgcGFuZWwuZ3JpZC5taW5vci55ID0gZWxlbWVudF9saW5lKGNvbG91ciA9IGdyYXkoMC42KSxsaW5ldHlwZSA9IDIpLAogICAgICAgICAgICBwYW5lbC5vbnRvcCA9IFRSVUUpCiAgfQogIAogIHAxID0gcDEgKyBjb29yZF9jYXJ0ZXNpYW4oeGxpbT14bGltaXRzLCB5bGltPXlsaW1pdHMsZXhwYW5kID0gRkFMU0UpCiAgCiAgaWYgKCFtaXNzaW5nKHdyYXApKSB7CiAgICBwMSA9IHAxICsgZmFjZXRfd3JhcChhcy5mb3JtdWxhKHdyYXApKQogIH0KICAKICByZXR1cm4ocDEpCn0KICAKYGBgCgoKYGBge3J9CnJlcHJlc2VudGF0aW9ucyA9IGMoJ2Nncl92YXJLb2RlcicsJ3ZhcktvZGVzJywnY2dyX2lkZWx1Y3MnKQptb2RlbHMgPSBjKCd2aXRfbGFyZ2VfcGF0Y2gzMl8yMjQnLCdpZ19yZXNuZXh0MTAxXzMyeDhkJywnZmlhbm5hY2EyMDE4JywnYXJpYXMyMDIyJykKcmFua3MgPSBjKCdzcGVjaWVzJywnZ2VudXMnLCdmYW1pbHknKQpgYGAKCgpOb3cgbGV0J3MgcGxvdCBnZW51cy1sZXZlbCBhY2N1cmFjeSBmb3IgYWxsIG1vZGVsczoKCgpgYGB7ciwgbWVzc2FnZSA9IEZBTFNFLCB3YXJuaW5nID0gRkFMU0V9CnJlc3VsdHMgPSBsaXN0KCkKc3VtbWFyaWVzID0gbGlzdCgpCnByZWNpc2lvbl9yZWNhbGwgPSBsaXN0KCkKcGxvdHMgPSBsaXN0KCkKCmZvciAocmVwIGluIHJlcHJlc2VudGF0aW9ucyl7CiAgZm9yIChtb2QgaW4gbW9kZWxzKXsKICAgIGlmIChyZXAgIT0gJ2Nncl9pZGVsdWNzJyApewogICAgICByZXN1bHRzW1twYXN0ZShyZXAsbW9kLHNlcD0nKycpXV0gPSByZWFkX2FuZF9wcm9jZXNzX3h2YWwocGFzdGUoJ3Jlc3VsdHMnLHJlcCxtb2Qsc2VwPSdfJykpCiAgICB9IGVsc2UgewogICAgICByZXN1bHRzW1twYXN0ZShyZXAsbW9kLHNlcD0nKycpXV0gPSByZWFkX2FuZF9wcm9jZXNzX3h2YWwocGFzdGUoJ3Jlc3VsdHMnLHJlcCxtb2Qsc2VwPSdfJyksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXN1bHRzW1twYXN0ZSgnY2dyX3ZhcktvZGVyJyxtb2Qsc2VwPScrJyldXSkKICAgIH0KICAgIAogICAgZm9yIChyayBpbiByYW5rcyl7CiAgICAgIHN1bW1hcmllc1tbcGFzdGUocmsscmVwLG1vZCxzZXA9JysnKV1dID0gc3VtbWFyaXplX3Jlc3VsdHMocmVzdWx0c1tbcGFzdGUocmVwLG1vZCxzZXA9JysnKV1dLHJrKQogICAgICBwcmVjaXNpb25fcmVjYWxsW1twYXN0ZShyayxyZXAsbW9kLHNlcD0nKycpXV0gPSBjYWxjdWxhdGVfcHJlY2lzaW9uX3JlY2FsbChyZXN1bHRzW1twYXN0ZShyZXAsbW9kLHNlcD0nKycpXV0scmspCiAgICAgIHBsb3RzW1twYXN0ZShyayxyZXAsbW9kLHNlcD0nKycpXV0gID0gc3VwcHJlc3NNZXNzYWdlcyh7cGxvdF9hcmVhKHN1bW1hcmllc1tbcGFzdGUocmsscmVwLG1vZCxzZXA9JysnKV1dLCBwYXN0ZShyayxyZXAsbW9kKSwgcmVsYXRpdmUgPSBUUlVFKX0pCiAgICB9CiAgfQp9CmBgYAoKTGV0J3Mgbm93IGxvb2sgYXQgYWxsIHBsb3RzLgoKYGBge3J9CnBsb3RzCmBgYAoKRnVuY3Rpb24gdG8gYXJyYW5nZSBwbG90cyBuaWNlbHk6CmBgYHtyfQpsaWJyYXJ5KGdncGxvdDIpCmxpYnJhcnkocGF0Y2h3b3JrKQoKYXJyYW5nZV90YXhfcGxvdHMgPC0gZnVuY3Rpb24ocGxvdF9saXN0LCB0YXhfbGV2ZWwgPSAic3BlY2llcyIpIHsKICAjIFZhbGlkYXRlIHRheF9sZXZlbAogIHZhbGlkX2xldmVscyA8LSBjKCJzcGVjaWVzIiwgImdlbnVzIiwgImZhbWlseSIpCiAgaWYgKCF0YXhfbGV2ZWwgJWluJSB2YWxpZF9sZXZlbHMpIHsKICAgIHN0b3AoInRheF9sZXZlbCBtdXN0IGJlIG9uZSBvZjogIiwgcGFzdGUodmFsaWRfbGV2ZWxzLCBjb2xsYXBzZSA9ICIsICIpKQogIH0KICAKICAjIEdldCBuYW1lcyBvZiBwbG90cyBmb3Igc3BlY2lmaWVkIHRheG9ub21pYyBsZXZlbAogIHRheF9uYW1lcyA8LSBuYW1lcyhwbG90X2xpc3QpW2dyZXAocGFzdGUwKCJeIiwgdGF4X2xldmVsLCAiXFwrIiksIG5hbWVzKHBsb3RfbGlzdCkpXQogIAogICMgQ3JlYXRlIG1hcHBpbmcgZm9yIG9yZGVyaW5nCiAgbW9kZWxzIDwtIGMoInZpdF9sYXJnZV9wYXRjaDMyXzIyNCIsICJpZ19yZXNuZXh0MTAxXzMyeDhkIiwgImZpYW5uYWNhMjAxOCIsICJhcmlhczIwMjIiKQogIHJlcHJlc2VudGF0aW9ucyA8LSBjKCJjZ3JfaWRlbHVjcyIsICJjZ3JfdmFyS29kZXIiLCAidmFyS29kZXMiKQogIAogICMgQ3JlYXRlIGVtcHR5IG1hdHJpeCB0byBzdG9yZSBwbG90IGluZGljZXMKICBwbG90X21hdHJpeCA8LSBtYXRyaXgoTkEsIG5yb3cgPSBsZW5ndGgocmVwcmVzZW50YXRpb25zKSwgbmNvbCA9IGxlbmd0aChtb2RlbHMpKQogIHJvd25hbWVzKHBsb3RfbWF0cml4KSA8LSByZXByZXNlbnRhdGlvbnMKICBjb2xuYW1lcyhwbG90X21hdHJpeCkgPC0gbW9kZWxzCiAgCiAgIyBGaWxsIG1hdHJpeCB3aXRoIHBsb3QgaW5kaWNlcwogIGZvciAocmVwIGluIHJlcHJlc2VudGF0aW9ucykgewogICAgZm9yIChtb2QgaW4gbW9kZWxzKSB7CiAgICAgIHBsb3RfbmFtZSA8LSB0YXhfbmFtZXNbZ3JlcChwYXN0ZTAocmVwLCAiLioiLCBtb2QsICIkIiksIHRheF9uYW1lcyldCiAgICAgIGlmIChsZW5ndGgocGxvdF9uYW1lKSA+IDApIHsKICAgICAgICBwbG90X21hdHJpeFtyZXAsIG1vZF0gPC0gd2hpY2gobmFtZXMocGxvdF9saXN0KSA9PSBwbG90X25hbWUpCiAgICAgIH0KICAgIH0KICB9CiAgCiAgIyBFeHRyYWN0IHBsb3RzIGluIGNvcnJlY3Qgb3JkZXIKICBwbG90X2luZGljZXMgPC0gYXMudmVjdG9yKHQocGxvdF9tYXRyaXgpKQogIHNlbGVjdGVkX3Bsb3RzIDwtIHBsb3RfbGlzdFtwbG90X2luZGljZXNdCiAgCiAgIyBDcmVhdGUgdGhlIGxheW91dCBtYW51YWxseQogIGNvbWJpbmVkX3Bsb3QgPC0gc2VsZWN0ZWRfcGxvdHNbWzFdXQogIGZvcihpIGluIDI6bGVuZ3RoKHNlbGVjdGVkX3Bsb3RzKSkgewogICAgY29tYmluZWRfcGxvdCA8LSBjb21iaW5lZF9wbG90ICsgc2VsZWN0ZWRfcGxvdHNbW2ldXQogIH0KICAKICAjIEFwcGx5IGxheW91dCBhbmQgdGhlbWUKICBjb21iaW5lZF9wbG90IDwtIGNvbWJpbmVkX3Bsb3QgKyAKICAgIHBsb3RfbGF5b3V0KG5jb2wgPSA0LCBndWlkZXMgPSAiY29sbGVjdCIpICYKICAgIHRoZW1lKAogICAgICBheGlzLnRleHQueCA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgYXhpcy50aWNrcy54ID0gZWxlbWVudF9ibGFuaygpLAogICAgICBheGlzLnRpdGxlID0gZWxlbWVudF9ibGFuaygpLAogICAgICBwbG90LnRpdGxlID0gZWxlbWVudF9ibGFuaygpLAogICAgICB0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemU9OCksCiAgICAgIGxlZ2VuZC5wb3NpdGlvbiA9ICdib3R0b20nCiAgICApCiAgCiAgIyBBZGQgYmFjayBuZWNlc3NhcnkgYXhpcyBlbGVtZW50cwogIGZvcihpIGluIHNlcV9hbG9uZyhzZWxlY3RlZF9wbG90cykpIHsKICAgICMgTGVmdCBjb2x1bW46IGFkZCB5LWF4aXMgdGV4dAogICAgaWYoaSAlaW4lIHNlcSgxLCA5LCBieSA9IDQpKSB7CiAgICAgIGNvbWJpbmVkX3Bsb3RbW2ldXSA8LSBjb21iaW5lZF9wbG90W1tpXV0gKyAKICAgICAgICB0aGVtZShheGlzLnRleHQueSA9IGVsZW1lbnRfdGV4dCgpKQogICAgfSBlbHNlIHsKICAgICAgY29tYmluZWRfcGxvdFtbaV1dIDwtIGNvbWJpbmVkX3Bsb3RbW2ldXSArIAogICAgICAgIHRoZW1lKGF4aXMudGV4dC55ID0gZWxlbWVudF9ibGFuaygpKQogICAgfQogICAgCiAgICAjIEJvdHRvbSByb3c6IGFkZCB4LWF4aXMgdGV4dCBhdCA0NSBkZWdyZWVzCiAgICBpZihpICVpbiUgOToxMikgewogICAgICBjb21iaW5lZF9wbG90W1tpXV0gPC0gY29tYmluZWRfcGxvdFtbaV1dICsgCiAgICAgICAgdGhlbWUoCiAgICAgICAgICBheGlzLnRleHQueCA9IGVsZW1lbnRfdGV4dChhbmdsZSA9IDQ1LCBoanVzdCA9IDEsdmp1c3Q9MSksCiAgICAgICAgICBheGlzLnRpY2tzLnggPSBlbGVtZW50X2xpbmUoKQogICAgICAgICkKICAgIH0KICB9CiAgCiAgcmV0dXJuKGNvbWJpbmVkX3Bsb3QpCn0KCiMgRXhhbXBsZSB1c2FnZToKIyBzcGVjaWVzX3Bsb3QgPC0gYXJyYW5nZV90YXhfcGxvdHMocGxvdF9saXN0LCAic3BlY2llcyIpCiMgZ2dzYXZlKCJzcGVjaWVzX3Bsb3RzLnBkZiIsIHNwZWNpZXNfcGxvdCwgd2lkdGggPSAxNiwgaGVpZ2h0ID0gMTIpCmBgYApTcGVjaWVzOgpgYGB7cn0KYXJyYW5nZV90YXhfcGxvdHMocGxvdHMsICJzcGVjaWVzIikKZ2dzYXZlKGRldmljZSA9ICdwZGYnLGZpbGVuYW1lID0gJ3NwZWNpZXNfY29tcGFyaXNvbi5wZGYnLHdpZHRoID0gMTUwLGhlaWdodCA9IDEzMCx1bml0cyA9ICdtbScpCmBgYAoKYGBge3J9CmFycmFuZ2VfdGF4X3Bsb3RzKHBsb3RzLCAiZ2VudXMiKQpgYGAKCmBgYHtyfQphcnJhbmdlX3RheF9wbG90cyhwbG90cywgImZhbWlseSIpCmBgYAoKCgoKTm93IGxldCdzIGNvbXBhcmUgcHJlY2lzaW9uIGFuZCByZWNhbGwgZm9yIGVhY2ggdGF4b25vbWljIGxldmVsLgpGaXJzdCwgc3BlY2llczoKYGBge3J9CgpvcHRpb25zKHRpYmJsZS5wcmludF9tYXggPSBJbmYpIAoKZGYgPSBpbWFwX2RmcihwcmVjaXNpb25fcmVjYWxsLCB+IG11dGF0ZSgueCwgbGlzdF9lbGVtZW50ID0gLnkpKSAlPiUKICBzZXBhcmF0ZShsaXN0X2VsZW1lbnQsIGludG8gPSBjKCJ0YXhvbm9teSIsICJyZXByZXNlbnRhdGlvbiIsICJtb2RlbCIpLCBzZXAgPSAiXFwrIiwgZXh0cmEgPSAibWVyZ2UiLCBmaWxsID0gInJpZ2h0IikgJT4lCiAgc2VsZWN0KC10YXhvbm9teSkgJT4lCiAgIGFycmFuZ2UodGF4b25vbWljX2xldmVsLGRlc2MoRjFfc2NvcmUpKQoKc3BsaXRfZGZzIDwtIHNwbGl0KGRmLCBkZiR0YXhvbm9taWNfbGV2ZWwpCgpzcGxpdF9kZnMKYGBgCgpJdCBzZWVtcyB0aGUgbXVsdGktbGF5ZXIgcGVyY2VwdHJvbiAoYXJpYXMyMDIyKSBoYWQgdmVyeSBsb3cgYWNjdXJhY3kuIExldCdzIGhhdmUgYSBsb29rIGF0IHRoZSBkZXRhaWxzIHRvIHVuZGVyc3RhbmQ6CgpgYGB7cn0KcmVzdWx0cyRgdmFyS29kZXMrYXJpYXMyMDIyYApgYGAKCkl0IHNlZW1zIHRoZSBjb3JyZWN0IHRheGEgbWF5IGhhdmUgaGlnaGVyIHByb2JhYmlsaXR5LCBidXQgbm90IGhpZ2ggZW5vdWdoIHRvIHBhc3Mgb3VyIDAuNyB0aHJlc2hvbGQuIE9uIHRoZSBvdGhlciBoYW5kLCBpbmNvcnJlY3QgdGF4YSBoYXZlIGdlbmVyYWxseSBsb3dlciBwcm9iYWJpbGl0eSwgYnV0IHByZXR0eSBoaWdoIHN0aWxsICgwLjMtMC41KS4gU28gdGhlIG1vZGVsIGhhcyBzb21lIHRyb3VibGUgZGlzY3JpbWluYXRpbmcgY2xhc3NlcyBpbiBhIG11bHRpbGFiZWwgbW9kZWwuCgpMZXQncyBub3cgc2F2ZSB0aGUgY29tcGFyaXNvbiB0YWJsZSBhcyBhIGNzdiB0byBhZGQgYXMgYSBzdXBwbGVtZW50IHRvIHRoZSBwYXBlci4KYGBge3J9CndyaXRlX2NzdihkZiwgJ2FyY2hfcmVwX3Jlc3VsdHMuY3N2JykKYGBgCgo=